package SortSummary;

/*
*   插入排序
*       排序步骤：
*           1.对于第n次循环来说，前n个数据是有序的
*           2.将第n+1个数据从后向前遍历，插入对应的位置
*           3.重复上述步骤，直到遍历完成数组
*       时间复杂度：O(n^2)
*       空间复杂度：O(1)
*       稳定性：稳定
* */

class InsertSort {
    static void insertSort(int[] nums){
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j>0;j--){
                if(nums[j]<nums[j-1]){
                    int num = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = num;
                }else{
                    break;
                }
            }
        }
    }
}
